def dp_activity_selector(s,f):
    n=len(s)
    s.append(f[-1]+1)
    s.insert(0,-1)
    f.append(-1)
    f.insert(0,0)
    dic={}
    no={}
    for i in xrange(0,n+1):
        dic[i,i+1]=set()
        no[i,i+1]=0
    for l in xrange(2,n+2): #index diff from 2..n+1
        for i in xrange(0,n-l+2): #0..n-l+1
            j=i+l
            no[i,j]=0
            dic[i,j]=set()
            for k in xrange(i+1,j):
                if s[k]>=f[i] and f[k]<=s[j]:
                    if no[i,k]+1+no[k,j]>no[i,j]:
                        no[i,j]=no[i,k]+1+no[k,j]
                        dic[i,j]=dic[i,k] | set([k]) | dic[k,j]
    return dic[0,n+1], no[0,n+1]

if __name__=='__main__':
    s=[1,3,0,5,3,5,6,8,8,2,12]
    f=[4,5,6,7,8,9,10,11,12,13,14]
    print 's:', s
    print 'f:', f
    maxset,no=dp_activity_selector(s,f)
    print 'ans:', sorted(list(maxset))
